#include <stdio.h>
#include <stdlib.h>
#include <vector>
//  Definition for singly-linked list.
struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};

void reorderList(ListNode *head) {
    if(head == NULL || head->next == NULL)
            return;
    ListNode *p1, *p2, *p3;
    std::vector<ListNode*> location;
    std::vector<ListNode*>::iterator it;
    p1 = head;
    while(p1 != NULL)
    {
        location.insert(location.begin(), p1);
        p1 = p1->next;
    }

    p1 = head;
    it = location.begin();
    p2 = *(it++);
    p3 = *(it);

    while(it!= location.end() && p2 != p1 && p2 != p1->next)
    {
        p3->next = NULL;
        p2->next = p1->next;
        p1->next = p2;

        p1 = p2->next;
        p2 = *(it++);
        p3 = *(it);
    }
}

ListNode* createList(int* a, int length)
{
    if(length <= 0)
        return NULL;
    ListNode *head, *p1, *p2;
    int i = 1;
    p1 = (ListNode*)malloc(sizeof(ListNode));
    p1->val = a[0];
    p1->next = NULL;
    head = p1;
    p2 = p1;
    while(i < length)
    {
        p1 = (ListNode*)malloc(sizeof(ListNode));
        p1->val = a[i++];
        p1->next = NULL;
        p2->next = p1;
        p2 = p2->next;
    }
    return head;
}

void printList(ListNode *head)
{
    if (head == NULL)
    {
        printf("This list is NULL\n");
        return;
    }

    ListNode *p1;
    p1 = head;
    int i = 1;
    while(p1 != NULL)
    {
        printf("%d %d\n", i++, p1->val);
        p1 = p1->next;
    }
    printf("\n");
}


int main(int argc, char const *argv[])
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    ListNode *l;
    l = createList(a, sizeof(a)/sizeof(int));
    printList(l);
    reorderList(l);
    printList(l);
    return 0;
}